public class code02s {
    public ListNode mergeKLists(ListNode[] lists) {
        // 解法二：进行分治合并
        // 要进行分治和并，需要先针对当前的数组进行分割
        // 之后再来针对这个数组进行两两合并
        // 专门实现一个方法对数组进行分配操作
        return merge(lists, 0, lists.length - 1);
    }

    public ListNode merge(ListNode[] lists, int left, int right) {
        // 通过递归来找到合适到数组进行返回
        // 设置递归返回条件
        if(left == right) {
            return lists[left];
        }
        // 当出现左侧的值比右侧的值大时，返回 null
        if(left > right) {
            return null;
        }
        // 将找到中间值
        int mid = (left + right) / 2;

        // 通过递归分别向数组的左右两侧进行寻找，以找到合适的数组
        return mergeTwo(merge(lists, left, mid), merge(lists, mid + 1, right));
    }

    public ListNode mergeTwo(ListNode list1, ListNode list2) {
        // 首先针对两边传递来的数组元素进行判断
        // 获取到不为空的一部分
        if(list1 == null || list2 == null) {
            return list1 == null? list2 : list1;
        }

        // 创建出一个新的节点，以此来重组返回结果
        ListNode head = new ListNode(0);
        ListNode flag = head;
        // 定义两个指针，分别指向两个单独的链表
        ListNode cur1 = list1;
        ListNode cur2 = list2;

        // 针对对称位置的值进行大小判断
        while(cur1 != null && cur2 != null) {
            if(cur1.val < cur2.val) {
                flag.next = cur1;
                cur1 = cur1.next;
            } else {
                flag.next = cur2;
                cur2 = cur2.next;
            }
            // 让flag标签向后移动
            flag = flag.next;
        }

        // 针对对称之外的数据进行处理
        if(cur1 == null) {
            flag.next = cur2;
        } else {
            flag.next = cur1;
        }

        // 拼接完成，返回最终结果
        return head.next;
    }
}
